package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.LinkedList;

public class _1306_jump_game {
    
    static class bfs {
        public boolean canReach(int[] arr, int start) {
            int n = arr.length;
            boolean[] visited = new boolean[n];
            LinkedList<Integer> q = new LinkedList<>();
            q.offer(start);
            while (!q.isEmpty()) {
                int pos = q.pop();
                if (pos >= n || pos < 0 || visited[pos]) continue;
                if (arr[pos] == 0) return true;
                visited[pos] = true;
                q.offer(pos + arr[pos]);
                q.offer(pos - arr[pos]);
            }
            return false;
        }
    }
    
    static class dfs {
        public boolean canReach(int[] arr, int start) {
            return dfs(arr, new boolean[arr.length], start);
        }
        boolean dfs(int[] arr, boolean[] visited, int i) {
            if (i >= arr.length || i < 0 || visited[i]) return false;
            if (arr[i] == 0) return true;
            visited[i] = true;
            return dfs(arr, visited, i + arr[i]) || dfs(arr, visited, i - arr[i]);
        }
    }
    
}
